|
In mathematics and computer science, a stack-sortable permutation (also called a tree permutation)〔 is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees. ==Sorting with a stack== The problem of sorting an input sequence using a stack was first posed by , who gave the following linear time algorithm (closely related to algorithms for the later all nearest smaller values problem): *Initialize an empty stack *For each input value ''x'': * *While the stack is nonempty and ''x'' is larger than the top item on the stack, pop the stack to the output * *Push ''x'' onto the stack *While the stack is nonempty, pop it to the output Knuth observed that this algorithm correctly sorts some input sequences, and fails to sort others. For instance, the sequence 3,2,1 is correctly sorted: the three elements are all pushed onto the stack, and then popped in the order 1,2,3. However, the sequence 2,3,1 is not correctly sorted: the algorithm first pushes 2, and pops it when it sees the larger input value 3, causing 2 to be output before 1 rather than after it. Because this algorithm is a comparison sort, its success or failure does not depend on the numerical values of the input sequence, but only on their relative order; that is, an input may be described by the permutation needed to form that input from a sorted sequence of the same length. Knuth characterized the permutations that this algorithm correctly sorts as being exactly the permutations that do not contain the permutation pattern 231: three elements ''x'', ''y'', and ''z'', appearing in the input in that respective order, with ''z'' < ''x'' < ''y''. Moreover, he observed that, if the algorithm fails to sort an input, then that input cannot be sorted with a single stack. As well as inspiring much subsequent work on sorting using more complicated systems of stacks and related data structures,〔; ; ; ; . See also the many additional references given by Bóna.〕 Knuth's research kicked off the study of permutation patterns and of permutation classes defined by forbidden patterns. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Stack-sortable permutation」の詳細全文を読む スポンサード リンク
|